ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

*******************

ТЕМА:  ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

********************

ЗАДАЧА 1. Решение задачи методом динамического программирования.

********************

В горной лесистой местности проложена сеть дорог, проходящих через ряд населенных пунктов. На схемах указаны расположение населенных пунктов и потребное количество топлива для перемещения между ними, зависящее от расстояния между пунктами, характера местности и от качества дороги.

Требуется найти оптимальную траекторию перемещения из пункта А в пункт В, обеспечивающую наименьший расход топлива.

 

Вариант  7

Решение:

Естественным шагом процесса в данной задаче является перемещение системы из одного промежуточного пункта в другой. Система характеризуется параметром х – расходом топлива при движении из данного пункта в пункт В. Управлением на i –ом шаге U_i является выбор одного из возможных направлений движения из данного пункта. Необходимо найти оптимальное управление U=(U₁, U₂, …, U_n) — маршрут движения от пункта А до пункта В, при котором расход топлива на весь путь был бы минимален: X =x_i.

I этап. Предварительная (условная) оптимизация.

1.  Начнем с последнего шага процесса, т.е. с ближайших от пункта В точек — 7, 8 и 9.

— из точки 7 в пункт В можно попасть только напрямую с расходом топлива 7 ед.  Отметим это направление пунктирной линией (полуоптимальное управление), величину соответствующего расхода запишем в кружке.;

— из точки 9 в пункт В можно попасть двумя путями:

напрямую               —  с расходом 6 ед.;

через точку 8          —    (5+7) =   12 ед.

Меньший расход топлива (6 ед.) при движении из точки 9 напрямую в точку В. Выберем это направление в качестве полуоптимального управления и отметим пунктирной линией, величину соответствующего расхода запишем в кружке.

— из точки 8 возможны также два направления движения:

напрямую               —   расход  7 ед.;

через  точку 9         —    (5+6) = 11 ед.;

Предпочтительным является  движение прямо, расход 7 ед.

2. Перейдем  к  следующему от конца шагу — к точкам 5 и 6.

— из точки 6 к пункту В можно двигаться:

через  точку 8         —   (5 + 7) = 12 ед.;

через точку 9        —    (5+ 6) = 11 ед.

Предпочтительным является  движение через точку 9,  суммарный расход —   11 ед.

— из точки 5 к пункту В можно двигаться:

через точку 6       —     (6+11) = 17 ед.;

через точку 7     —     (2+9) = 11 ед.;

через точку 8     —      (6+7) = 13 ед.

Предпочтительным является движение через точку 7, суммарный расход — 11 ед.

3. На следующем шаге рассмотрим точки 3 и 4:

— из точки 4 к пункту В можно двигаться только через точку 6    — расход —  (5+11) = 16 ед.;

— из точки  3 к пункту В можно двигаться:

через точку 4    —  (3+16) = 19 ед.;

через точку 5    —  (5+11) = 16 ед.;

Предпочтительным направлением является движение через точку 5, суммарный расход 16 ед.

4. На следующем шаге рассмотрим точки 1 и 2:

— из точки 1 к пункту В можно двигаться тремя путями:

через точку 7    — расход —  (7+9) = 16 ед.;

через точку 5    — расход —  (4+11) = 15 ед.;

через точку 3    — расход —  (2+16) = 18 ед.;

Предпочтительным направлением является движение через точку 5, суммарный расход 15 ед.

— из точки  2 к пункту В можно двигаться:

через точку 3    —  (5+16) = 21 ед.;

через точку 4    —  (4+16) = 20 ед.;

Предпочтительным направлением является движение через точку 4, суммарный расход 20 ед.,

4.  Переходим к исходной точке А.  Из нее к пункту В можно двигаться в трех направлениях:

— через точку 1, суммарный расход равен  (4+15) = 19 ед.,

— через точку 3, суммарный расход равен  (5+16) = 21 ед.,

— через точку 2, суммарный расход равен   (3+20) =23 ед.

Предпочтительным является движение через точку 1, суммарный расход при этом минимальный и равен 19 ед.

II этап. Окончательная (безусловная) оптимизация.

Анализируя  результаты предыдущего — этапа предварительной (условной) оптимизации,  получим, что из точки А нужно двигаться к  точке 1, затем  к точке 5 и т.д. Нарисуем «цепочку» оптимального маршрута                                     А   Þ   1    Þ   5   Þ    8   Þ   В

Оптимальный маршрут нарисуем сплошной линией,

Расход топлива, необходимый  для движения по этому маршруту, равный 19 единицам, является минимальным.

Оптимальный маршрут    А   Þ  1   Þ  5  Þ   7  Þ  В,

Минимальный расход топлива 19 ед.

 

Вариант 8.

Решение:

 

Естественным шагом процесса в данной задаче является перемещение системы из одного промежуточного пункта в другой. Система характеризуется параметром х – расходом топлива при движении из данного пункта в пункт В. Управлением на i –ом шаге U_i является выбор одного из возможных направлений движения из данного пункта. Необходимо найти оптимальное управление U=(U₁, U₂, …, U_n) — маршрут движения от пункта А до пункта В, при котором расход топлива на весь путь был бы минимален: X =x_i.

I этап. Предварительная (условная) оптимизация.

1.  Начнем с последнего шага процесса, т.е. с ближайших от пункта В точек — 7, 8 и 9.

— из точки 7 в пункт В можно попасть только напрямую с расходом топлива 9 ед.  Отметим это направление пунктирной линией (полуоптимальное управление), величину соответствующего расхода запишем в кружке.;

— из точки 9 в пункт В можно попасть двумя путями:

напрямую               —  с расходом 6 ед.;

через точку 8          —    (4+7) =   11 ед.

Меньший расход топлива (6 ед.) при движении из точки 9 напрямую в точку В. Выберем это направление в качестве полуоптимального управления и отметим пунктирной линией, величину соответствующего расхода запишем в кружке.

— из точки 8 возможны также два направления движения:

напрямую               —   расход  7 ед.;

через  точку 9         —    (4+6) = 10 ед.;

Предпочтительным является  движение прямо, расход 7 ед.

2. Перейдем  к  следующему от конца шагу — к точкам 5 и 6.

— из точки 6 к пункту В можно двигаться:

через  точку 8         —   (6 + 7) = 13 ед.;

через точку 9        —    (6+ 6) = 12 ед.

Предпочтительным является  движение через точку 9,  суммарный расход —   12 ед.

— из точки 5 к пункту В можно двигаться:

через точку 6       —     (5+12) = 17 ед.;

через точку 7     —     (4+9) = 13 ед.;

через точку 8     —      (5+7) = 12 ед.

Предпочтительным является движение через точку 8, суммарный расход — 12 ед.

3. На следующем шаге рассмотрим точки 3 и 4:

— из точки 4 к пункту В можно двигаться только через точку 6    — расход —  (4+12) = 16 ед.;

— из точки  3 к пункту В можно двигаться:

через точку 4    —  (6+16) = 22 ед.;

через точку 5    —  (4+12) = 16 ед.;

Предпочтительным направлением является движение через точку 5, суммарный расход 16 ед.

4. На следующем шаге рассмотрим точки 1 и 2:

— из точки 1 к пункту В можно двигаться тремя путями:

через точку 7    — расход —  (8+9) = 17 ед.;

через точку 5    — расход —  (8+12) = 20 ед.;

через точку 3    — расход —  (3+16) = 19 ед.;

Предпочтительным направлением является движение через точку 3, суммарный расход 19 ед.

— из точки  2 к пункту В можно двигаться:

через точку 3    —  (4+16) = 20 ед.;

через точку 4    —  (5+16) = 21 ед.;

Предпочтительным направлением является движение через точку 3, суммарный расход 20 ед.,

4.  Переходим к исходной точке А.  Из нее к пункту В можно двигаться в трех направлениях:

— через точку 1, суммарный расход равен  (6+17) = 23 ед.,

— через точку 3, суммарный расход равен  (7+16) = 23 ед.,

— через точку 2, суммарный расход равен   (2+20) =22 ед.

Предпочтительным является движение через точку 2, суммарный расход при этом минимальный и равен 22 ед.

II этап. Окончательная (безусловная) оптимизация.

Анализируя  результаты предыдущего — этапа предварительной (условной) оптимизации,  получим, что из точки А нужно двигаться к  точке 2, затем  к точке 3 и т.д. Нарисуем «цепочку» оптимального маршрута                                     А   Þ   2    Þ   3   Þ    5   Þ8   Þ   В

Оптимальный маршрут нарисуем сплошной линией,

Расход топлива, необходимый  для движения по этому маршруту, равный 22 единицам, является минимальным.

Оптимальный маршрут    А   Þ  2   Þ  3  Þ   5  Þ  8  Þ  В,

Минимальный расход топлива 22 ед.

 

 

Вариант    10.

Решение:

Естественным шагом процесса в данной задаче является перемещение системы из одного промежуточного пункта в другой. Система характеризуется параметром х – расходом топлива при движении из данного пункта в пункт В. Управлением на i –ом шаге U_i является выбор одного из возможных направлений движения из данного пункта. Необходимо найти оптимальное управление U=(U₁, U₂, …, U_n) — маршрут движения от пункта А до пункта В, при котором расход топлива на весь путь был бы минимален: X =x_i.

I этап. Предварительная (условная) оптимизация.

1.  Начнем с последнего шага процесса, т.е. с ближайших от пункта В точек — 7, 8 и 9.

— из точки 7 в пункт В можно попасть двумя путями:

напрямую                —   с расходом 7 ед.;

через точку 8           —    (2 + 8) = 10 ед.

Меньший расход топлива (7 ед.) при движении из точки 7 напрямую в точку В. Выберем это направление в качестве полуоптимального управления и отметим пунктирной линией, величину соответствующего расхода запишем в кружке.

— из точки 9 в пункт В можно попасть также двумя путями:

напрямую               —  с расходом 4 ед.;

через точку 8          —    (5+8) =   13 ед.

Полуоптимальное управление — движение напрямую, расход — 4 ед.

— из точки 8 возможны три направления движения:

напрямую               —   расход  8 ед.;

через  точку 9         —    (5+4) = 9 ед.;

через  точку 7         —    (2+7) = 9 ед.

Предпочтительным является  движение прямо, расход 8 ед.

2. Перейдем  к  следующему от конца шагу — к точкам 4, 5 и 6.

— из точки 6 к пункту В можно двигаться:

через  точку 8         —   (8 + 2) = 10 ед.;

через точку 7        —    (4+ 7) = 11 ед.

Предпочтительным является  движение через точку 8,  суммарный расход —   10 ед.

— из точки 4 к пункту В можно двигаться:

через точку 7         —    (7+ 7)  = 14 ед.;

через точку 6       —    (3+10) = 13 ед.

Предпочтительное направление движения  — через точку 6, суммарный расход равен 13 ед.

— из точки 5 к пункту В можно двигаться:

через точку 6       —     (3+10) = 13 ед.;

через точку 8     —     (5+8) = 13 ед.;

через точку 9     —      (7+4) = 11 ед.

Предпочтительным является движение через точку 9, суммарный расход — 11 ед.

3. На следующем шаге рассмотрим точки 1, 2 и 3:

— из точки 3 к пункту В можно двигаться:

через точку 4    —  (2+13) = 15 ед.;

через точку 6    —  (6+10) = 16 ед.;

через точку 5    —  (5+11)= 16 ед.

Предпочтительным является  движение  через точку 4, суммарный расход — 15 ед.

— из точки  1 к пункту В можно двигаться:

через точку 4    —  (4+13) = 17 ед.;

через точку 3    —  (6+15) = 21 ед.;

Предпочтительным направлением является движение через точку 4, суммарный расход 17 ед.,

— из точки 2 к пункту В можно двигаться:

через точку 3    —   (3+15) = 18 ед.;

через точку 5    —   (8+11) = 19 ед.

Предпочтительным является  движение  через точку 3, суммарный расход 18 ед.,

4.  Переходим к исходной точке А.  Из нее к пункту В можно двигаться в трех направлениях:

— через точку 1, суммарный расход равен  (3+17) = 20 ед.,

— через точку 3, суммарный расход равен  (9+15) = 24 ед.,

— через точку 2, суммарный расход равен   (6+18) =24 ед.

Предпочтительным является движение через точку 1, суммарный расход при этом минимальный и равен 20 ед.

II этап. Окончательная (безусловная) оптимизация.

Анализируя  результаты предыдущего — этапа предварительной (условной) оптимизации,  начиная с точки А, поучим, что из точки А нужно двигаться к  точке 2, затем  к точке 3 и т.д. Нарисуем «цепочку» оптимального маршрута                   А   Þ   1    Þ   4   Þ   6   Þ   8   Þ   В

Оптимальный маршрут нарисуем сплошной линией,

Расход топлива, необходимый  для движения по этому маршруту, равный 20 единицам, является минимальным.

Оптимальный маршрут    А   Þ  1   Þ  4  Þ  6  Þ  8  Þ  В,

Минимальный расход топлива 20 ед.